package arithmetic;

import org.junit.jupiter.api.Test;

/**
 * @author jiangfeng on 2022/3/14
 */
public class HuiwenString {
    // 找出字符传里的最长回文串

    public static void main(String[] args) {
        System.out.println( findMaxHuiwen("abc"));
        System.out.println( findMaxHuiwen("aba"));
        System.out.println( findMaxHuiwen("cbc"));
        System.out.println( findMaxHuiwen("cbca"));
        System.out.println( findMaxHuiwen("acbca"));
        System.out.println("----动态规划----");
        System.out.println( findMaxHuiwen2("acbca"));
        System.out.println( findMaxHuiwen2("ac"));
        System.out.println( findMaxHuiwen2("aa"));
        System.out.println( findMaxHuiwen2("abc"));
        System.out.println( findMaxHuiwen2("aba"));
    }

    /**
     * 暴力破解法  时机复杂度: ,n的三次放
     * @param txt
     * @return
     */
    public static String findMaxHuiwen(String txt) {
        char[] chars = txt.toCharArray();
        int maxLen = -1;
        String result = "";
        for (int i = 0; i < chars.length; i++) {
            for (int j = i; j < chars.length; j++) {
                boolean huiwen = isHuiwen(chars, i, j);
                int length = j - i;
                if (huiwen && length > maxLen) {
                    result = new String(chars, i, j - i + 1);
                    maxLen = length;
                }
            }
        }
        return result;
    }

    public static boolean isHuiwen(char[] chars,int start,int end){
        if (end - start < 0) {
            return false;
        }
        if (end == start ) {
            return true;
        }
        while(start<=end){
            if(chars[start]!=chars[end]){
                return false;
            }
            start++;
            end--;
        }
        return true;
    }

    /**
     * 动态规划
     * 状态转换方程:
     * 如果 子串是回文则且 父串两边也是回文
     * dp[i,j] = dp[i+1,j-1] && str[i] == str[j]
     */
    public static String findMaxHuiwen2(String txt) {
        // 快速返回
        if (txt.length() == 1) {
            return txt;
        }
        char[] chars = txt.toCharArray();
        if (chars.length == 2) {
            return chars[0] == chars[1] ? txt : txt.substring(1);
        }

        boolean[][] arr = new boolean[chars.length][chars.length];

        // 初始化所有斜对角的都是true
        for (int i = 0; i < arr.length; i++) {
            arr[i][i] = true;
        }
        // 默认第一个就是回文
        int start = 0, maxLen = 1;

        // 先枚举串的长度
        for (int L = 2; L <= chars.length; L++) {
            for (int i = 0; i < arr.length; i++) {
                // 右边界 j-i+1 =L
                int j = L + i - 1;
                // 超过边界
                if (j > chars.length - 1) {
                    break;
                }
                if (chars[i] != chars[j]) {
                    arr[i][j] = false;
                } else {
                    // L 为2,3 直接就是回文
                    if (L < 4) {
                        arr[i][j] = true;
                    } else {
                        arr[i][j] = arr[i + 1][j - 1];
                    }
                    if (arr[i][j] && maxLen < L) {
                        // 记录
                        maxLen = L;
                        start = i;
                    }
                }

            }
        }
        return new String(chars, start, maxLen);
    }


    // 动态规划
    public int countSubstrings(String s) {
        int length = s.length();
        if(length==1){
            return 1;
        }
        char[] chars = s.toCharArray();
        if(length==2){
            return 2 + (chars[0]==chars[1]?1:0);
        }
        // 动态规划转化方程 n<=m , a[n,m] = a[n]==a[m] && a[n+1,m-1]

        boolean a[][] = new boolean[length][length];
        int count = 0;
        // 初始化一下
        for(int i =0;i<length;i++){
            a[i][i] = true;
            count++;
            if(i+1<length && chars[i]==chars[i+1]){
                a[i][i+1] = true;
                count++;
            }
        }

        // 字符长度
        for(int currLen = 3; currLen<=length;currLen++){
            int fromLeft = currLen/2;
            // 中心点
            for(int i =fromLeft;i< length;i++){
                // 左右有超界则 立即跳出
                int l = i-fromLeft;
                // 右边界
                int r = currLen+l-1;
                if(l<0 || r>=length){
                    continue;
                }
                if(chars[l] == chars[r]  && a[l+1][r-1] ){
                    a[l][r] = true;
                    count++;
                }
            }
        }
        return count;
    }

    @Test
    public void test(){
        System.out.println(countSubstrings("abc"));
    }


    // 中心扩展法
    // 动态规划
    public int countSubstrings2(String s) {
        int length = s.length();
        char[] chars = s.toCharArray();
        // 中心点一共 s + s -1 个位置
        int size = length*2 -1;
        int result = 0;
        for (int i = 0; i < size; i++) {
            int left = i/2;
            // 长度 0 都是偶数, 偶数是1位开始, 奇数是两位开始;  奇数处理为加一个 即两个字母开始
            int right = i/2 + ((i&1)!=0?1:0);
            while(left>=0 && right<length && chars[left] ==chars[right]){
                result++;
                left--;
                right++;
            }
        }
        return result;
    }

    @Test
    public void test2(){
        System.out.println(countSubstrings2("abc"));
        System.out.println(countSubstrings2("aba"));
        System.out.println(countSubstrings2("aaa"));
        System.out.println(countSubstrings2("aabb"));
    }


    /**
     * 最大回文子串
     * @param s
     * @return
     */
    public String longestPalindrome(String s) {
        char[] c = s.toCharArray();
        int lenght = c.length;s.length();
        int maxSize = 0;
        String result= null;
        int centerSize = 2*lenght-1;
        for(int i = 0;i<centerSize;i++){
            int left = i/2;
            int right = i/2 +((i%2==0)?0:1);
            while(left>=0&&right<lenght && c[left]==c[right] ){
                int l =right-left+1;
                if(maxSize<l){
                    result = new String(c,left,l);
                    maxSize = l;
                }
                left--;
                right++;
            }
        }
        return result;
    }

}
